package leetcode_day._2023._12;

import java.util.PriorityQueue;

/**
 * 1962. 移除石子使总数最小
 * 算法：优先队列
 *
 * @author yezh
 * @date 2023/12/23 17:18
 */
public class _23 {

    public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        for (int pile : piles) queue.offer(pile);
        while (k-- > 0 && !queue.isEmpty()) queue.offer((queue.poll() + 1) / 2);
        int ans = 0;
        while (!queue.isEmpty()) ans += queue.poll();
        return ans;
    }

    public int minStoneSum_heap(int[] piles, int k) {
        heapify(piles);
        while (k-- > 0 && piles[0] > 1) {
            piles[0] = (piles[0] + 1) / 2;
            sink(piles, 0);
        }
        int ans = 0;
        for (int pile : piles) ans += pile;
        return ans;
    }

    void heapify(int[] h) {
        for (int i = h.length / 2 - 1; i >= 0; i--) sink(h, i);
    }

    void sink(int[] h, int i) {
        int n = h.length;
        while (i * 2 + 1 < n) {
            int j = 2 * i + 1;
            if (j + 1 < n && h[j + 1] > h[j]) ++j;
            if (h[j] <= h[i]) break;
            swap(h, i, j);
            i = j;
        }
    }

    void swap(int[] h, int i, int j) {
        int tmp = h[i];
        h[i] = h[j];
        h[j] = tmp;
    }

}
